package com.squirrel.michale.search5;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/19 7:29 PM
 * @company Michale Squirrel
 * @link
 * @description
 *
 * 局部最小
 * 问题：
 * 给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任
 *
 * 意一个局部最小出现的位置即可。
 *
 * 思路：
 * 1、arr长度为1时，arr[0]是局部最小。
 *
 *      arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；
 *
 * 2、如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；
 *
 * 3、如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。
 * ————————————————
 * 版权声明：本文为CSDN博主「behboyhiex」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
 * 原文链接：https://blog.csdn.net/behboyhiex/article/details/80759200
 */
public class Example003 {

    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    // 不一定有序才能二分，只要有一种排他性的原则出现，构建出可以排掉另外一边的逻辑，而且这种逻辑是正确的，就可以二分
}
